//
//  Problem1641.swift
//  TestProject
//
//  Created by 武侠 on 2021/2/20.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1641. 统计字典序元音字符串的数目
 给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。

 字符串 s 按 字典序排列 需要满足：对于所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。

 示例 1：
     输入：n = 1
     输出：5
     解释：仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"]
 示例 2：
     输入：n = 2
     输出：15
     解释：仅由元音组成的 15 个字典序字符串为
     ["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
     注意，"ea" 不是符合题意的字符串，因为 'e' 在字母表中的位置比 'a' 靠后
 示例 3：
     输入：n = 33
     输出：66045
 */
@objcMembers class Problem1641: NSObject {
    func solution() {
        print(countVowelStrings(2))
        print(countVowelStrings(33))
    }
    
    /*
     动态规划
     1: 创建一个二位数组 dp[5][len] （a, e, i, o, u）5个字母
     2: dp[2][3]: 以i为首字母，长度为3的字符串的个数
     3: dp[i][j] = dp[i][j-1] + ... + dp[4][j-1]
     */
    func countVowelStrings(_ n: Int) -> Int {
        if n == 1 {
            return 5
        }
        
        var dp = Array(repeating: Array(repeating: 0, count: n), count: 5)
        // 特例：设置n=1时的值
        for i in 0..<5 {
            dp[i][0] = 1
        }
        
        var result = 0
        for i in 1..<n {
            dp[0][i] = dp[0][i-1] + dp[1][i-1] + dp[2][i-1] + dp[3][i-1] + dp[4][i-1]
            dp[1][i] = dp[1][i-1] + dp[2][i-1] + dp[3][i-1] + dp[4][i-1]
            dp[2][i] = dp[2][i-1] + dp[3][i-1] + dp[4][i-1]
            dp[3][i] = dp[3][i-1] + dp[4][i-1]
            dp[4][i] = dp[4][i-1]
            if i == n-1 {
                result = dp[0][i] + dp[1][i] + dp[2][i] + dp[3][i] + dp[4][i]
            }
        }

        return 0
    }
}
